#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//struct ListNode {
//    int val;
//    struct ListNode* next;
//    
//};
//
//struct ListNode* reverseList(struct ListNode* head) {
//    struct ListNode* slow = NULL;
//    struct ListNode* fast = head;
//    while (fast)
//    {
//        struct ListNode* next = fast->next;
//        fast->next = slow;
//        slow = fast;
//        fast = next;
//    }
//    return slow;
//}
//
//void test()
//{
//    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    n1->val = 1;
//    n2->val = 2;
//    n3->val = 3;
//    n4->val = 4;
//    n5->val = 5;
//    n1->next = n2;
//    n2->next = n3;
//    n3->next = n4;
//    n4->next = n5;
//    n5->next = NULL;
//    struct ListNode* n = reverseList(n1);
//    while (n)
//    {
//        printf("%d ", n->val);
//        n = n->next;
//    }
//}
//
//int main()
//{
//    test();
//    return 0;
//}

//bool isValid(char* s) {
//    int length = 0;
//    while (s[length])
//        length++;
//    char* tmp = (char*)calloc(length, sizeof(char));
//    if (!tmp)
//    {
//        perror("calloc failed");
//        return 0;
//    }
//    char* ptr = tmp;
//    int i, j = 0;
//    for (i = 0; i < length; i++)
//    {
//        if ((s[i] == '(') || (s[i] == '{') || (s[i] == '['))
//        {
//            ptr[++j] = s[i];
//        }
//        else if ((s[i] == ptr[j] + 1) || (s[i] == ptr[j] + 2))
//        {
//            j--;
//        }
//        else
//        {
//            free(ptr);
//            ptr = NULL;
//            return 0;
//        }
//    }
//    if (!j)
//    {
//        free(ptr);
//        ptr = NULL;
//        return 1;
//    }
//
//    free(ptr);
//    ptr = NULL;
//    return 0;
//
//}
//
//int main()
//{
//    char arr[10] = "]{";
//    printf("%d", isValid(arr));
//    return 0;
//}

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>


typedef int QueDatatype;

typedef struct QueueNode
{
    QueDatatype val;
    struct QueueNode* next;
}QNode;

typedef struct Queue
{
    QNode* head;
    QNode* tail;
    int size;
}Que;

void QueInit(Que* q)
{
    assert(q);
    q->head = q->tail = NULL;
    q->size = 0;
}

void QueDestroy(Que* q)
{
    assert(q);
    QNode* cur = q->head;
    while (cur)
    {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    q->head = q->tail = NULL;
    q->size = 0;
}

int QueSize(Que* q)
{
    assert(q);

    return q->size;
}

bool QueIsempty(Que* q)
{
    assert(q);

    return QueSize(q) == 0;
}

void QuePop(Que* q)
{
    assert(q);
    assert(!QueIsempty(q));
    if (q->head->next == NULL)
    {
        free(q->head);
        q->head = q->tail = NULL;
    }
    else
    {
        QNode* next = q->head->next;
        free(q->head);
        q->head = next;
    }
    q->size--;
}

void QuePush(Que* q, QueDatatype x)
{
    assert(q);

    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (!newnode)
    {
        perror("malloc failed");
        return;
    }
    newnode->next = NULL;
    newnode->val = x;
    if (q->head == NULL)
    {
        q->head = q->tail = newnode;
    }
    else
    {
        q->tail->next = newnode;
        q->tail = newnode;
    }
    q->size++;
}

QueDatatype QuePeek(Que* q)
{
    assert(q);
    assert(!QueIsempty(q));

    return q->head->val;
}



typedef struct {
    Que q1;
    Que q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    if (!st)
    {
        perror("malloc failed");
        return NULL;
    }
    QueInit(&st->q1);
    QueInit(&st->q2);
    return st;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);
    if (!QueIsempty(&obj->q1))
    {
        QuePush(&obj->q1, x);
    }
    else
    {
        QuePush(&obj->q2, x);
    }
}

int myStackPop(MyStack* obj) {
    assert(obj);


    Que* empty = &obj->q1;
    Que* nonempty = &obj->q2;
    if (!QueIsempty(&obj->q1))
    {
        nonempty = &obj->q1;
        empty = &obj->q2;
    }

    while (QueSize(nonempty) > 1)
    {
        QuePush(empty, QuePeek(nonempty));
        QuePop(nonempty);
    }
    QueDatatype top = nonempty->head->val;
    QuePop(nonempty);
    return top;
}

int myStackTop(MyStack* obj) {
    assert(obj);

    Que* empty = &obj->q1;
    Que* nonempty = &obj->q2;
    if (!QueIsempty(&obj->q1))
    {
        nonempty = &obj->q1;
        empty = &obj->q2;
    }

    while (QueSize(nonempty) > 1)
    {
        QuePush(empty, QuePeek(nonempty));
        QuePop(nonempty);
    }
    QueDatatype top = QuePeek(nonempty);
    QuePush(empty, QuePeek(nonempty));
    QuePop(nonempty);
    return top;
}

bool myStackEmpty(MyStack* obj) {
    assert(obj);
    return QueIsempty(&obj->q1) && QueIsempty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    assert(obj);
    QueDestroy(&obj->q1);
    QueDestroy(&obj->q2);
    free(obj);
    obj = NULL;
}
//["MyStack","push","push","top","pop","pop","empty"]
//[[], [1], [2], [], [], [], []]
int main()
{
    MyStack* st =  myStackCreate();
    myStackPush(st, 1);
    myStackPush(st, 2);
    myStackTop(st);
    myStackPop(st);
    myStackPop(st);
    myStackEmpty(st);
    myStackFree(st);

    return 0;
}